iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 11
1

今天要介紹的是樹,大致的樣子如下圖,其中樹的每個元素都稱為節點,樹最上方的節點稱為根節點,而節點之間上層節點為下層節點的父節點,下層節點為上層節點的子節點,如果一個節點底下沒有任何的子節點,我們稱為葉節點

節點和其子節點可以構成子樹,如圖中的紅框部分。
一個節點的深度可由它祖先節點的數量推算出,例如14節點有25和34兩個祖先節點,其深度為2。
樹的高度則取決於所有節點深度的最大值,此圖高度為3。

樹(Tree)的應用例子

  • HTML DOM
  • Abstract Syntax Tree
  • 資料夾結構
  • JSON
  • 臉書留言回覆,會有很多層

二元樹(Binary tree) 和 二元搜尋樹(Binary Search Tree)

這兩種樹在資料結構中相當常見,因此來稍微介紹它們:

二元樹每個節點最多只有兩個分支(即不存在分支度大於2的節點)的樹結構,通常分支被稱作「左子樹」或「右子樹」。

二元搜尋樹是指一棵空樹或者具有下列性質的二元樹:

  • 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值
  • 若任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值
  • 任意節點的左、右子樹也分別為二元搜尋樹
  • 沒有鍵值相等的節點

二元搜尋樹還有以下兩點特性:

  • 節點資料是經過排序的
  • 彈性的資料大小,可以隨意新增節點

二元搜尋樹的範例圖:

二元搜尋樹相關操作的動畫可以參考此連結

二元搜尋樹還衍伸出各種的 Tree

例如以下這幾種 Tree,有機會再詳細介紹它們。

平衡二元搜尋樹

它是一種每個節點的左右兩子樹高度差都不超過一的二元樹,例如附圖左邊的樹就是平衡二元搜尋樹,因為左右子樹高度相差一,但右邊的樹左右子樹高度相差二,就不算是平衡二元搜尋樹。出現此類樹是為了避免出現某些子樹出現過深,而有些子樹卻只有一兩層的情況,讓所有葉子的深度趨於平衡,如此即使最糟的情況下時間複雜度也能降低至 O(log n)。

要對一個樹做平衡的話,可以參考維基百科 Tree rotation 樹旋轉

是對二元樹的一種操作,不影響元素的順序,但會改變樹的結構,將一個節點上移、一個節點下移。樹旋轉會改變樹的形狀,因此常被用來將較小的子樹下移、較大的子樹上移,從而降低樹的高度、提升許多樹操作的效率。

https://ithelp.ithome.com.tw/upload/images/20230114/20116883S2sM0EIMJB.png

平衡二元搜尋樹的範例如 Red Black Tree、AVL Tree 都是平衡二元搜尋樹。

AVL Tree: 每一個節點的左子樹高度-右子樹高度只能是 -1、0、1

完全二元樹(Complete binary tree) / 完滿二元樹(Full binary tree)

  • 完全二元樹: 除了最後一個階層的節點外,其他的節點都有兩個節點
  • 完滿二元樹: 每個節點有0或2個子節點

https://ithelp.ithome.com.tw/upload/images/20230304/20116883qN6xMLKnmu.png


在看完樹的介紹之後,我們來用 JavaScript 實作 樹吧!

先建立出節點和樹的類別出來:

class TreeNode {
  constructor(data, left = null, right = null) {
    this.data = data
    this.left = left
    this.right = right
  }
}

class Tree {
  constructor() {
    this.root = null
  }
}

之後透過新增節點,然後將節點加到節各節點的分支,便完成了

let n1 = new TreeNode(32);
let n2 = new TreeNode(92);
let n3 = new TreeNode(13);
let n4 = new TreeNode(44);
let n5 = new TreeNode(87);

let tree = new Tree();
tree.root = n1
n1.left = n2
n1.right = n3
n3.right = n4
n4.left = n5

產生的樹如下圖所示:

樹到這邊就完成實作,不過我們來試試多加一個 collect() 函式,將所有節點整理成陣列輸出

我們預設一開始的節點是root,然後節點陣列為空陣列,然後將目前找到的節點推入陣列,並將該節點的左右子節點作為參數,再次呼叫 collect() 函式進行遞迴。

class Tree {
  constructor() {
    this.root = null
  }

  // 使用遞迴去遍歷樹節點
  // 一開始的節點是root,然後節點陣列為空陣列
  collect(current = this.root, nodes = []) {
    if (current === null) {
      return nodes
    }
    nodes.push(current.data)

    this.collect(current.left, nodes)
    this.collect(current.right, nodes)
    return nodes
  }
}

用文字解說遞迴順序:

  1. current = this.root,也就是根節點50,推入陣列 nodes
  2. 找到根節點50的左節點43,推入陣列 nodes
  3. 節點43再找左節點,但為 null,無新增任何東西,右節點也一樣為 null
  4. 找到根節點50的右節點67,推入陣列 nodes
  5. 節點67再找左節點,但為 null,無新增任何東西,不過找到有右節點,為節點81,推入陣列 nodes
  6. 節點81找到左節點75,推入陣列 nodes,節點75左右子節點都是 null,便回傳最終的 nodes 陣列

這次實作的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day11-tree.js

二元搜尋樹的時間複雜度

  • 插入節點、搜尋節點、移除節點: 最佳、平均 O(log n),最差的狀況例如每層節點只有右節點的 Tree,或是都只有左節點的 Tree(形狀很奇怪XD) 為 O(n)

樹的走訪

樹的走訪主要分成兩種-BFS(廣度優先搜尋) & DFS(深度優先搜尋),Tree 和 Graph 都可以執行這兩個演算法。

Breadth-First Search(BFS,廣度優先搜尋)

按照 Tree 的層級由上層往下層遍歷,每層的節點都訪問過後,就會往下一層的節點訪問。

BFS 函式實作

使用 quque 去儲存每層的節點,visited 儲存要回傳的節點陣列。

  1. 第一層: 當前根節點為 10,將其子層的節點存在 queue
    quque: [6, 15]
    visited: [10]
//      10
//   6     15
// 3  8      20
  1. 第二層,到 6 節點,存 3、8
    quque: [15, 3, 8]
    visited: [10, 6]

  2. 第二層,到 15 節點
    quque: [3, 8, 20]
    visited: [10, 6, 15]

  3. 第三層
    quque: []
    visited: [10, 6, 15, 3, 8, 20]

將上面的概念轉換成程式碼,可以寫出以下函式:

BFS() {
  let node = this.root;
  const data = [], queue = [];
  queue.push(node);

  while (queue.length) {
    node = queue.shift();
    data.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return data;
}

Depth-First Search(DFS,深度優先搜尋)

從演算法的名字"深度"可以知道和 BFS 是相對的關係,BFS 是橫向的一層層掃過搜尋,而 DFS 的確是相反,是從樹根不斷往子樹節點往下搜尋(縱向),並且根據搜尋的順序還可以細分為以下幾種:

前序遍歷 (Preorder Traversal)

順序是根節點、左子節點、右子節點,根排在前面。

後序遍歷 (Postorder Traversal)

順序是左子節點、右子節點、根節點,根排在後面。

中序遍歷 (Inorder Traversal)

順序是左子節點、根節點、右子節點,根排在中間。

如果是遍歷的樹是二元搜尋樹的話,取出的節點會依照由小而大排序

https://ithelp.ithome.com.tw/upload/images/20230506/20116883AGXlEkHL7e.png

層序遍歷 (Level-order Traversal)

由根節點開始,到下層子節點,由左至右遍歷,並持續往下層遍歷至全部節點為止。可用 Queue 作為層序遍歷


Tree 的 BFS 和 DFS 比較

BFS

  • 常搭配 Queue 實作
  • 適合查找目標比較接近起始根節點的情況
  • 因為 BFS 會由上層往下層遍歷節點,故需要消耗較多記憶體儲存

DFS

  • 常搭配 Stack 實作
  • 適合查找目標比較遠離起始根節點的情況
  • 消耗較少記憶體儲存節點,但很深的(例如只有左節點那種) Tree 也會和 BFS 消耗得差不多

而兩者的時間複雜度都是 O(v + e),v 是節點數量,e 是邊的數量。

https://ithelp.ithome.com.tw/upload/images/20230112/20116883nY5goX5eeZ.png

以上就是這次的樹 (Tree) 介紹,明天將會介紹樹的一些相關操作函式!


上一篇
Day10-來介紹遞迴(Recursion)吧!
下一篇
Day12-資料結構-樹(Tree)的一些操作方法
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言